package org.laizili.misc.sort;

import java.util.Arrays;
import java.util.Random;

public class MergeSort {

    private int[] auxArr;

    // merge: [ll, lr], [rl, rr]
    private void merge(int[] arr, int ll, int lr, int rl, int rr) {
        int k = ll;
        int lp = ll;
        int rp = rl;
        while (lp <= lr && rp <= rr) {
            if (arr[lp] < arr[rp]) {
                auxArr[k++] = arr[lp++];
            } else {
                auxArr[k++] = arr[rp++];
            }
        }
        while (lp <= lr) {
            auxArr[k++] = arr[lp++];
        }
        while (rp <= rr)
            auxArr[k++] = arr[rp++];
        System.arraycopy(auxArr, ll, arr, ll, rr - ll + 1);
    }

    //[]
    public void sort0(int[] arr, int left, int right) {
        // 多于一个元素
        if (left < right) {
            int mid = (left + right) / 2;
            sort0(arr, left, mid);
            sort0(arr, mid + 1, right);
            merge(arr, left, mid, mid + 1, right);
        }
    }

    public void sort(int[] arr) {
        //
        auxArr = new int[arr.length];
        sort0(arr, 0, arr.length - 1);
    }

    //test case
    public static void main(String[] args) {
        final MergeSort mergeSort = new MergeSort();
        Random random = new Random();
        for (int i = 0; i < 10; i++) {
            int n = random.nextInt(10) + 10;
            int[] arr = new int[n];
            for (int j = 0; j < n; j++) {
                arr[j] = random.nextInt();
            }
            System.out.println(Arrays.toString(arr));
            final int[] newArr = Arrays.copyOf(arr, arr.length);
            mergeSort.sort(arr);
            Arrays.sort(newArr);
            System.out.println(Arrays.toString(arr));
            if (!Arrays.equals(arr, newArr)) {
                throw new IllegalStateException("算法逻辑错误");
            }
        }
    }
}
